/**
 * @package 正则表达式匹配
 * @description 给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
 * '.' 匹配任意单个字符
 * '*' 匹配零个或多个前面的那一个元素
 * 所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
 * @author liu <admin>
 */
export const title = '正则表达式匹配'

function matches(s: string, p: string, i: number, j: number): boolean {
  if (i === 0) return false
  if (p.charAt(j - 1) === '.') return true
  return s.charAt(i - 1) === p.charAt(j - 1)
}

/**
 * 动态分配解法
 * @param {string} s
 * @param {string} p
 * @returns {boolean}
 */
export function isMatch(s: string, p: string): boolean {
  const [m, n] = [s.length, p.length]
  if (!p.includes('*') && m !== n) return false
  const f: boolean[][] = Array.from({ length: m + 1 }, () => [])
  f[0][0] = true
  for (let i = 0; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (p.charAt(j - 1) === '*') {
        f[i][j] = f[i][j - 2]
        if (matches(s, p, i, j - 1)) {
          f[i][j] = f[i][j] || f[i - 1][j]
        }
      } else {
        if (matches(s, p, i, j)) {
          f[i][j] = f[i - 1][j - 1]
        }
      }
    }
  }

  return f[m][n] || false
}

/**
 * 正则
 * @param {string} s
 * @param {string} p
 * @returns {boolean}
 */
export function isMatch2(s: string, p: string): boolean {
  p = p.replace(/\*+/g, '*')
  return s.replace(new RegExp(p), '') ? false : true
}
